package DataStr.ex02;
public class stack03<T>{
    //成员变量
    private Node head;
    private Node last;
    private int N;
    public class Node{
        public T t;
        public Node next;
        public Node(T t,Node next){
            this.t=t;
            this.next=next;
        }
    }
    public stack03(){
        this.head=new Node(null,null);
        this.last=null;
        this.N=0;
    }
    //判断队列是否为空
    public boolean isEmpty(){
        return N==0;
    }
    //返回队列中元素个数
    public int size(){
        return N;
    }
    //向队列中插入元素t
    public void enqueue(T t){
        //当前尾节点为null
        if(last==null){
            last=new Node(t,null);
            head.next=last;
        }else {
            //当前尾节点不为null,将原先的last记录下来
            Node oldlast=last;
            //插入t创建新last节点，next为null
            last=new Node(t,null);
            //令原先last与现last连接
            oldlast.next=last;
        }
        //队列总数加一
        N++;
    }
    //从队列中拿出一个元素
    public T dequeue(){
        //首先先判断队列是否为空
        if(isEmpty()){
            return null;
        }
        //如果队列不为空，拿出一个元素，根据先进先出的特点，拿走的是首元结点
        //记录首元节点
        Node oldFirst=head.next;
        //使头结点连接原先首元节点的下一个节点
        head.next=oldFirst.next;
        //总数减一
        N--;
        //因为出队列是删数据，如果队列数据被删除完了，需要重置last=null；
        if(isEmpty()){
            last=null;
        }
        return oldFirst.t;
    }
}
